huge.hoo
CRDT 와 OT
Mar 11, 2024

Table of Contents

    서론

    구글 독스, 노션, 피그마 같은 애플리케이션에서는 동일한 페이지나 화면을 다수의 사용자가 동시에 편집할 수 있는 기능을 제공한다. 이러한 실시간 협업 애플리케이션은 여러명이 동시에 컨텐츠를 편집하더라도 결과적으로 동일한 내용으로 수렴(Convergence)하는 특징을 가진다. 이런 기술은 어떤 원리로 구현됐을까? 대표적인 기술로 OT(Operation Transformation) 와 CRDT(Conflict-free Replicated Data Types) 가 있다. 각 기술의 특징과 장단점을 아래에서 더 자세히 다뤄보겠다.

    OT

    OT : Operational Transformations (1989 ~ 2006)

    OT 는 2006년 정도까지 사용된 기술로 Google Docs 와 MS Office 에 사용됐다.

    crdt1.png


    OT 는 오퍼레이션(작업)이 이전 동작의 영향으로 다음 동작을 transform(변환) 시키는 것, 즉 두가지 작업이 거의 동시에 일어난다고 가정하면 첫번째 작업에 의해 두번째 작업이 영향을 받아 변경(transform)되는 것을 의미한다. 아래 이미지처럼 서로 다른 두명의 User가 HAT 문자열을 수정하는 상황을 가정해보자. 서버가 OT 방식으로 작업을 처리하면 어떤 결과가 나올까?

    User1 는 문자열 가장 앞에 C를 추가하고, User2 는 가장 처음의 문자 H를 삭제했다. 개별 유저로부터 발생한 operations 은 서버를 통해 처리되는데, 이 때 User1의 작업이 User2보다 먼저 수행된다고 가정하자. 문자 C 입력으로 그 이후의 모든 문자들은 모두 1씩 인덱스가 뒤로 밀리게 되고, 결과적으로 User2의 operations 은 두번째 문자 삭제로 인덱스가 보정되어 전달된다.

    즉 User2의 operation은 실제 의도한 것과는 조금 변경된(transform) 오퍼레이션으로 전달되어 문서 스트림에 적용된다.

    crdt2.png crdt3.png

    User1 의 operation 이 적용되면 기존 HAT 의 문자 배열 스트림은 인덱스값이 변경된다. 그렇기 때문에 H를 삭제하려고 한 User2 의 operation 은 delete at 0 에서 delete at 1 로 변경(transform) 되는 것이다.


    OT 의 단점

    위에서 언급한대로 Operation 의 수정(transformation)은 중앙 집중식 서버에서 수행된다. 이는 곧 단일 서버에서 operation 이 수행기 때문에 사용자가 몰릴 때는 시스템 과부하가 발생할 수도 있다. 라고 많은 문서에 나와있지만… 사실 구글 독스가 과부하된 걸 직접 경험한 적이 없어서 단점이 피부로 와닿지 않았다. 하지만 좀 더 생각해보면 실질적으로 문서를 저장하는 것도 아닌데 매 입력마다 서버로 데이터를 전송해야 한다. 특정 문서를 편집하고 있는 클라이언트 끼리만 통신하여 변경사항을 적용하고 최종 문서를 저장할 때만 서버로 전송되면 충분할텐데 말이다.

    CRDT

    CRDT: Conflict-free Replicated Data Types (2006 ~ present)

    2006년 이후 부터는 OT 를 대체하여 CRDT 방식이 더 곽광받고 있다. CRDT 의 장점은 동시성이 요구되는, 즉 실시간으로 협업해야 하는 클라이언트 끼리만 데이터를 교환하면 된다는 점이다. 이는 OT의 단점을 완벽히 보완하는 특징으로 서버에 대한 의존과 부하를 줄이는 효과와 각 유저들이 작업할 때 더 빠른 반응속도를 낼 수 있다.

    CRDT 는 conflic-free replicated data type` 의 약자로 충돌없는 복제된 데이터 타입을 의미한다. 복제된 데이터 타입이 무슨 의미일까? 서로 다른 컴퓨터(peer) 에 저장할 수 있는 데이터 구조의 한 타입이라 생각할 수 있다. 여기서 서로 다른 컴퓨터란 (피그마를 예를 들면) 동일한 피그마 페이지를 보고 있는 다수의 사용자를 의미한다.

    c각 피어는 자체 상태를 다른 피어를 확인하기 위한 네트워크 요청 없이 즉시 업데이트 할 수 있다. 다른 피어의 작업 내역에 따라 자신의 작업(operation)을 수정했던 OT 방식과 어떤 차이가 있는지 확연히 알 수 있다. 때문에 각 피어는 서로 다른 시간에 서로 다른 상태를 가질 수 있지만 결국 최종적으로 하나의 합의된 상태로 수렴(convergence)하게 된다.

    어떤 원리로 각 peer 는 하나의 상태로 수렴할 수 있을까? 아래 예시 이미지를 보자.

    crdt4.png

    User A : l 을 o 와 o 사이에 삽입한다.

    User B : ? 를 o 와 ! 사이에 삽입한다.

    이전의 OT 는 기존 문자열의 인덱스 값을 모두 수정하면서 새로운 값을 삽입했다. 하지만 CRDT 는 문자열의 각 문자에 identifier 라는 유니크한 값을 부여한다. 즉 OT 처럼 문자열이 수정될 때 마다 인덱스가 수정되는 것이 아니라, 문자열의 변경이 있어도 초기의 유니크 값을 그대로 유지할 수 있다.

    crdt5.png

    어떤 변경사항이 생기면 순서와 상관없이 상태를 수정할 수 있다. 작업의 순서를 유지하는 서버도 없기 때문에 중앙 서버도 필요하지 않다. 문서를 편집하는 유저끼리만(peer to peer) 데이터를 교환하면 되므로 속도가 빠르고 서버 부하를 줄일 수 있는 장점이 있다.

    CRDT 의 삭제는 아래처럼 동작한다. 동일한 문자를 삭제하는 경우라면 분명 동일한 identifier 를 가지는 문자를 삭제하게 된다. 위치 기반이 아닌 id 기반으로 삭제가 이뤄지기에 이미 삭제된 id 는 더 이상 존재하지 않아 중복 삭제 문제도 발생하지 않는다.

    crdt6.png


    CRDT 의 한계

    그럼 CRDT는 그저 완벽하기만 할까?

    1. 우선 각 피어에 문자스트림과 더불어 identifier를 추가로 (tree 구조로)저장하기 때문에 많은 메모리를 소모한다.

    2. CRDT 는 중앙 집중 서버없이 각 피어끼리 통신한다고 앞서 말했다. 그럼 각 피어끼리 통신이 가능하지 않는 상황이라면?.?네트워크 연결이 불가능하면 각 피어는 자신의 변경사항을 네트워크 복구 후에 다른 피어들과 동기화하여 전파할 수 있다.물론 복구 시간이 오래 걸릴수록 데이터 일관성을 유지하는 데 걸리는 시간도 늘어날 수 있다.

    3. CRDT 는 시간(순서)기반이 아닌 고유 ID를 기반으로 동작하기 때문에 merge 과정에서 실시간성이 모호해질 수 있다. 아래 예시처럼 동기화 결과 문자열이 섞여 의도치 않은 결과물이 나올 수 있다. 이런 문제를 해결하기 위해 다양한 알고리즘 기법(Logoot, LSEQ, RGA, Treedoc, WOOT, Astrong etc)이 나오고 있지만, 어떤 케이스는 사실상 근본적인 해결이 힘들기도 하다.

    결론

    CRDT와 OT는 모두 분산 시스템에서 데이터 일관성을 유지하고 동시 수정 충돌을 해결하기 위한 방법론으로 사용된다. 각각의 방법은 고유한 특징과 장단점을 가지고 있으나 결국 앞으로도 OT 와 관련된 작업은 필요없을 것으로 예상된다. OT의 모든 기능이 CRDT에 대입할 수 있지만, 그 반대는 불가능하기 때문이다. 학계에서는 CRDT와 관련된 학문적인 부분은 거의 완성되었고 이제 훌륭한 구현체가 필요한 시점이라고 볼 수 있다.